package com.sicheng.蓝桥.练习题.线段树;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/24 19:28
 */
@SuppressWarnings("all")
//网上Cpp代码改造来学习 尝试了解基本原理之后，形成自己的模板
public class Look {


    static int N = 100005;
    static long a[] = new long[N];        //a[N]储存原数组
    static long lazy[] = new long[N << 2];//lazy用来记录该节点的每个数值应该加多少
    static Tree[] tree = new Tree[N << 2];
    static int n, q;

    class Tree {
        int l, r;
        long sum;

        int mid() {
            return (l + r) >> 1;
        }
    }

    void pushUp(int rt) {
        tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
    }


    /**
     * @param l  左届
     * @param r  右届
     * @param rt 树编号
     */
    void build(int l, int r, int rt) {
        tree[rt] = new Tree();
        tree[rt].l = l;
        tree[rt].r = r;
        if (l == r) {
            tree[rt].sum = a[l];
            return;
        }
        int m = tree[rt].mid();
        build(l, m, (rt << 1));
        build(m + 1, r, (rt << 1 | 1));
        pushUp(rt);
    }

    /**
     * @param rt 树编号
     * @param m  rt的区间长度
     */
    void pushDown(int rt, int m) {
        if (lazy[rt] > 0) {
            lazy[rt << 1] += lazy[rt];
            lazy[rt << 1 | 1] += lazy[rt];
            tree[rt << 1].sum += lazy[rt] * (m - (m >> 1));
            tree[rt << 1 | 1].sum += lazy[rt] * (m >> 1);
            lazy[rt] = 0;
        }
    }

    /**
     * @param c  区间的元素都加c
     * @param l
     * @param r
     * @param rt 从树顶1号开始搜索
     */
    void update(long c, int l, int r, int rt) {
        if (tree[rt].l == l && tree[rt].r == r) {
            lazy[rt] += c;
            tree[rt].sum += c * (r - l + 1);
            return;
        }
        int m = tree[rt].mid();
        pushDown(rt, tree[rt].r - tree[rt].l + 1);
        if (r <= m)
            update(c, l, r, rt << 1);
        else if (l > m)
            update(c, l, r, rt << 1 | 1);
        else {
            update(c, l, m, rt << 1);
            update(c, m + 1, r, rt << 1 | 1);
        }
        pushUp(rt);
    }

    void update(int c, int l, int r) {
        update(c, l, r, 1);
    }

    long query(int l, int r) {
        return query(l, r, 1);
    }

    long query(int l, int r, int rt) {
        if (l == tree[rt].l && r == tree[rt].r) {
            return tree[rt].sum;
        }
        int m = tree[rt].mid();
        pushDown(rt, tree[rt].r - tree[rt].l + 1);
        long res = 0;
        if (r <= m)
            res += query(l, r, rt << 1);
        else if (l > m)
            res += query(l, r, rt << 1 | 1);
        else {
            res += query(l, m, rt << 1);
            res += query(m + 1, r, rt << 1 | 1);
        }
        return res;
    }

    void build() {
        build(1, n, 1);
    }

    /**
     * 8
     * 1 2 3 4 5 6 7 8
     */
    public static void main(String[] args) {
        Look look = new Look();
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        look.build();
        look.update(4, 1, 4);
        look.update(2, 4, 5);
        System.out.println(look.query(2, 3));
    }
}
